package ljl.alg.hot100;

import commons.ListNode;

import java.util.LinkedList;

/**
* 这个题你看着简单其实没那么简单
* */
public class _234_palindrome_link_list {
    
    // 感觉递归比栈好，但是怎么写呢？
    // 不会，先用栈吧
    public boolean isPalindrome3(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode p = head;
        int len = 0;
        while (p != null) {
            stack.push(p);
            p = p.next;
            len++;
        }
        int i = 0;
        while (i < len / 2 + 1) {
            if (head.val != stack.pop().val)
                return false;
            head = head.next;
            i++;
        }
        return true;
    }
    
    // 还有个解法，是复制到数组，然后双指针
    // 我倒是没想到这么搞，感觉也还行其实
    
    /*
    * 你心心念念的递归解法
    * 非常的神秘！
    *
    * 空间复杂度也是 n，和拷贝到数组一样
    * */
    ListNode front;
    boolean recursive(ListNode cur) {
        if (cur != null) {
            if (!recursive(cur.next))
                return false;
            // 当 cur == head 且走到这一行时 front 已经是最后一个元素了
            // 确实不好想
            if (cur.val != front.val)
                return false;
            front = front.next;
        }
        return true;
    }
    public boolean isPalindrome2(ListNode head) {
        front = head;
        return recursive(head);
    }
    
    /*
    * 正宗解法应该是快慢指针的
    * 不对，还得反转链表，更麻烦了！
    *
    * 挺好，通过了
    * */
    public boolean isPalindrome1(ListNode head) {
        ListNode slow = head, fast = head;
        // 如果两个元素 slow 指向第二个
        // 如果三个元素，slow 指向第二个，不行！
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
        // 所以只能找到前半部分求 next 了，死脑筋，唉
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 现在如果是在中点后面那个，就翻转 slow 往后的部分，然后和 head 开始比
        ListNode p = reverse(slow.next);
        while (p != null) {
            if (p.val != head.val)
                return false;
            p = p.next;
            head = head.next;
        }
        
        return true;
    }
    ListNode reverse(ListNode node) {
        ListNode prev = null, cur = node;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
}
